package interview;


import java.util.ArrayList;

/**
 * 使用数组+链表实现一个HashMap
 * get put delete
 *
 */
public class CusHashMap {

    class Node{
        private Object key;
        private Object value;
        private Node next;
        private Node prev;

        public Node(Object key, Object value){
            this.key = key;
            this.value = value;
        }
    }

    // 数组:根据下标可以查询到 链表

    // 链表:存储具体的Node
    private ArrayList<Node> nodes;

    // 长度
    private int capi;

    // 成员个数
    // 构造方法
    public CusHashMap(){
    }

    // PUT
    public void put(Object key, Object value){
        // 获取ket的 hash，然后 取 % 查找数组中的下标的位置
        // 新的节点
        Node newNode = new Node(key, value);
        int hash = handleHashCode(key);
        //
        int position = hash % capi;
        // 根据数组下标从List中获取到的 链表头节点
        Node originNode = nodes.get(position);
        if(originNode == null){
            nodes.set(position, newNode);
        }else{
            // 遍历链表 查看链表中的Node是否存在key 的equals 相等的Node，如果相等，替换，否则 append到链表尾部
            Node equalsNode = searchEqualsByKey(originNode, key);
            if(equalsNode == null){
                // 一个可以获取链表尾节点的方法
                Node tail = getTailNode(originNode);
                tail.next = newNode;
                newNode.prev = tail;
            }else{
                // 查找到了对应的 key equals重复的Node节点，将该节点替换为新的Node
                newNode.next = equalsNode.next;
                newNode.prev = equalsNode.prev;
                equalsNode.prev.next = newNode;
            }
        }


    }

    /**
     * @TODO 可以跟遍历链表结合一下，现在遍历了两次
     * @param originNode
     * @return
     */
    private Node getTailNode(Node originNode) {
        while (originNode.next != null) originNode = originNode.next;
        return originNode;
    }

    // 遍历链表 查看链表中的Node是否存在key 的equals 相等的Node，如果相等，替换，否则 append到链表尾部
    private Node searchEqualsByKey(Node node, Object key) {
        while(node != null){
            if(node.key.equals(key)){
                return node;
            }else{
                node = node.next;
            }
        }
        return null;
    }

    // GET

    //DELETE


    public static void main(String[] args) {

    }

    private int handleHashCode(Object k){
        return  0;
    }



}
